import java.util.*;


public class FindLadders {
  
    public List<String> wordList;
    public boolean flag = false;        //找到重点时置为true, 之后的递归可以快速返回
    public HashSet<String> visit = new HashSet<>();  //储存访问过的节点
    public List<String> ans = new ArrayList<>();
    public HashSet<String> unable = new HashSet<>();  //储存回溯的节点，回溯了说明该节点下的通路不符合题意

    public List<String> findLadders(String beginWord, String endWord, List<String> wordList) {
        if(!wordList.contains(endWord)) return ans;
        this.wordList = wordList;
        List<String> path = new ArrayList<>();
        dfs(beginWord, path,endWord);
        return ans;
    }

    public void dfs(String s, List<String> path, String end){
        if(flag || visit.contains(s) || unable.contains(s)) return;     //如果已找到 || 已访问 || 已回溯  则直接返回
        path.add(s);    
        visit.add(s);
        if(s.equals(end)){      //找到终点
            flag = true;
            ans = new ArrayList<>(path);
            return;
        }
        for(int i = 0; i < wordList.size(); i++){   //遍历所有存在的节点
            if(isConnect(s, wordList.get(i))){      //如果与当前节点连通，则递归下去
                dfs(wordList.get(i),path,end);
            }
        }
        path.remove(path.size()-1);         //回溯，临时路径中删除访问的节点
        visit.remove(s);                    //回溯，访问节点置为未访问
        unable.add(s);                      //回溯时保存当前节点，该节点之后的通路均不满足题意
    }

    
    public boolean isConnect(String start, String end){  //用于判断两个节点之间是否连通，即start和end字符串之间只有一个字符不同
        int count = 0;
        for(int i = 0; i < start.length(); i++){
            if(start.charAt(i)!=end.charAt(i)){
                count++;
            }
            if(count > 1) break;
        }
        return count == 1;
    }
  //  暴力解法
  // public List<String> findLadders(String beginWord, String endWord, List<String> wordList) {
  //   Set<String> set = new HashSet<>(wordList);
  //   for(String word : wordList){
  //     set.add(word);
  //   }
  //   if(!set.contains(endWord)){
  //     return new ArrayList<>();
  //   }
  //   List<String> res = new ArrayList<>();
  //   res.add(beginWord);
  //   Set<String> visited = new HashSet<>();
  //   Map<String, List<String>> memopMap = new HashMap<>();
  //   visited.add(beginWord);
    
  //   return dfs(beginWord, endWord, set, visited, res, memopMap);
  // }

  private List<String> dfs(String a, String b, Set<String> wordListSet, Set<String> visited, List<String> res, Map<String, List<String>> memopMap) {
    if(a.equals(b)){
      return new ArrayList<>(res);
    }
    if(memopMap.containsKey(a)){
      return memopMap.get(a);
    }
    for(int i = 0; i< a.length(); i++){
      for(char c = 'a'; c<='z'; c++){
        if(a.charAt(i) == c) continue;
        String next = a.substring(0,i) + c + a.substring(i+1);
        if(visited.contains(next) && memopMap.containsKey(next)){
          return memopMap.get(next);
        }else if (visited.contains(next)) {
          continue;
        }
        if(!wordListSet.contains(next)) continue;
        visited.add(next);
        res.add(next);
        List<String> list = dfs(next, b, wordListSet, visited, res, memopMap);
        if(!list.isEmpty()){
          memopMap.put(a, list);
          return list;
        }
        res.remove(res.size() - 1);
        visited.remove(next);
      }
    }
    
    return new ArrayList<>();
  }

  public static void main(String[] args) {
    FindLadders fl = new FindLadders();
    String beginWord = "hit";
    String endWord = "cog";
    List<String> wordList = new ArrayList<>();
    wordList.add("hot");
    wordList.add("dot");
    wordList.add("dog");
    wordList.add("lot");
    wordList.add("log");
    wordList.add("cog");
    List<String> result = fl.findLadders(beginWord, endWord, wordList);
    System.out.println(result);
  }
}

// 给定字典中的两个词，长度相等。写一个方法，把一个词转换成另一个词， 但是一次只能改变一个字符。每一步得到的新词都必须能在字典中找到。

// 编写一个程序，返回一个可能的转换序列。如有多个可能的转换序列，你可以返回任何一个。

// 示例 1：

// 输入：
// beginWord = "hit",
// endWord = "cog",
// wordList = ["hot","dot","dog","lot","log","cog"]

// 输出：
// ["hit","hot","dot","lot","log","cog"]
// 示例 2：

// 输入：
// beginWord = "hit"
// endWord = "cog"
// wordList = ["hot","dot","dog","lot","log"]

// 输出：[]

// 解释：endWord "cog" 不在字典中，所以不存在符合要求的转换序列。